#include <stdio.h>
#include <stdlib.h>
//二叉树链式结构
//内容：创建二叉树（二级指针），遍历二叉树（递归）
typedef char ElemType;
//二叉树结点声明
typedef struct bitree
{
    ElemType data;
    struct bitree *lchild;  //左孩子
    struct bitree *rchild;  //右孩子
}BiTree;
//二叉树字符数组
char expr[]="ABDH#K###E##CFI###G#J##";
int i=0;
//二叉树的创建
void creatbitree(BiTree **t) //t是二级指针，指向结点地址的指针
{                            //每新创建一个结点，结点地址都要改变（重新开辟），结点内容也不同
    ElemType symbol;         //如果还是一级指针，堆内存开辟空间并赋值给一级指针，但是一级指针只是函数局部变量
    symbol=expr[i++];        //在这个creatbitree函数中创建了二叉树，但并没有传回给主函数
    if(symbol=='#')
    {
        *t=NULL;
    }
    else 
    {
        *t=(BiTree *)malloc(sizeof(BiTree));
        (*t)->data=symbol;
        creatbitree(&(*t)->lchild);
        creatbitree(&(*t)->rchild);
    }
}
//前序遍历二叉树：根左右
void prebitree(BiTree *t)
{
    if(t==NULL)
    {
        return;
    }
    printf("%c",t->data);
    prebitree(t->lchild);
    prebitree(t->rchild);
}
//中序遍历二叉树：左根右
void inbitree(BiTree *t)
{
    if(t==NULL)
    {
        return;
    }
    inbitree(t->lchild);
    printf("%c",t->data);
    inbitree(t->rchild);
}
//后序遍历二叉树：左右根
void behbitree(BiTree *t)
{
    if(t==NULL)
    {
        return;
    }
    behbitree(t->lchild);
    behbitree(t->rchild);
    printf("%c",t->data);
}
int main()
{
    BiTree *t=NULL;//t是指向结点的指针，因为结构体不会开辟空间，所以把t初始化为空指针
    creatbitree(&t);//二级指针，因为既要改变t的值还要改变t指向内容的值，若是#则为空指针(没有结点)，若是字符则开辟空间并赋值(存入结点)
    prebitree(t);
    printf("\n");
    inbitree(t);
    printf("\n");
    behbitree(t);
    printf("\n");
    return 0;
}
//输出：
//ABDHKECFIGJ
//HKDBEAIFCGJ
//KHDEBIFJGCA
//对于creatbitree函数二级指针使用的理解：
//首先，这里不使用一级指针直接传参是因为无法真正改变一级指针的值，一级指针是指向结点的指针
//也就是说一级指针中存放结点的地址，二叉树有很多结点，那么就会有很多不同的结点地址
//在creatbitree函数中，通过在堆内存中开辟空间来给一级指针赋值，一级指针在每次递归中都会存放不同的地址，从而形成二叉树
//但是值得注意的是一级指针也是变量，即使在creatbitree函数中多次被赋值，但主函数中一级指针并未改变它的值，意思是creatbitree函数中的二叉树并没有传回来
//为了能真正改变一级指针的值，就要用二级指针了
//那就有个疑问？为什么之前创建节点不需要二级指针呢？
//因为前面创建的一级指针指向头节点，它不需要改变，一直指向头节点，每创建一个新节点也会有一个新的指针指向
//并且在初始化时，初始化函数是有返回值的，把指向头节点的一级指针的值返回到主函数并存入主函数中的一级指针变量
//但是在二叉树创建中，由于使用递归算法，那个传进creatbitree函数的一级指针每次递归都要指向新结点，也就是要存放一个新开辟的地址
//所以只能使用二级指针来改变一级指针的值
//总结来说，creatbitree函数相当于前面的初始化，二叉树在creatbitree函数中创建了，但若想传回主函数就要用二级指针


//又重新思考了一下，如果把creatbitree函数就当成初始化，然后写成 BiTree *t=creatbitree(); 然后creatbitree函数返回头结点（根节点）的指针，这样可行吗？
//当实际去写时会发现写到递归时由于没有参数而无法递归，写不下去了，所以这种方法不可行
//所以creatbitree函数必须有参数